0% completed
Problem Statement
Given an array of positive integers nums (0-indexed) and an integer k, return the maximum possible score of a good subarray.
The score of a subarray (i, j) is defined as min(nums[i], nums[i+1], ..., nums[j]) * (j - i + 1). If any subarray follows i <= k <= j condition, it is considered as good subarray.
Examples
Example 1:
- Input:
nums = [1, 2, 3, 4, 5], k = 2 - Expected Output:
9 - Justification: The best subarray is
[3, 4, 5], where the minimum value is3, and the length is3. The score is3 * 3 = 9.
Example 2:
- Input:
nums = [8, 1, 2, 4, 3], k = 3 - Expected Output:
6 - Justification: The best subarray is
[2, 4, 3], where the minimum value is2, and the length is3. The score is2 * 3 = 6.
Example 3:
- Input:
nums = [4, 6, 4, 7, 2, 5, 1], k = 4 - Expected Output:
12 - Justification: The optimal subarray is
[4, 6, 4, 7, 2, 5], with the minimum value2and length6. Therefore, the score is2 * 6 = 12.
Solution
To solve this problem, we start by considering the element at index k as the initial "good" subarray. Since the minimum value of a subarray containing only one element is the element itself, and the length is 1, the initial score is the value of nums[k]. We then expand this subarray to include adjacent elements on either side, continuously updating our calculation of the minimum value in the expanded subarray and its length. This process continues as long as expanding the subarray increases the score.
The key to this approach is to utilize a two-pointer technique, where we start with both pointers at k and expand outwards, ensuring that we always include k in our subarray. This ensures that all potential "good" subarrays are considered. The reason this method is effective is that it directly targets the constraint that k must always be within the subarray, allowing us to efficiently explore all relevant options without unnecessary comparisons or calculations.
Step-by-Step Algorithm
-
Initialize pointers and variables:
- Start with two pointers
leftandrightat the indexk. This marks the beginning of the subarray to consider. - Initialize
minValto the value at indexkinnums, since this is the only element in the current subarray. - Set
maxScorealso to the value at indexk, as this is the score of the subarray consisting of only thekth element.
- Start with two pointers
-
Expand the subarray:
- Use a loop to expand the subarray to the left and right, as long as there are elements to consider (i.e.,
left > 0orright < nums.length - 1). - Determine whether to move
leftorrightbased on boundary conditions and the values adjacent to the current subarray:- If
leftis at the start (0), onlyrightcan be moved. - If
rightis at the end (nums.length - 1), onlyleftcan be moved. - Otherwise, move the pointer (
leftorright) towards the side with the higher adjacent value to potentially increase the subarray's score.
- If
- Use a loop to expand the subarray to the left and right, as long as there are elements to consider (i.e.,
-
Update minimum value and score:
- After each expansion, update
minValto the minimum value in the new subarray. This involves comparingminValwith the new elements included in the subarray. - Calculate the score of the current subarray (
minVal * (right - left + 1)) and updatemaxScoreif this new score is higher than the currentmaxScore.
- After each expansion, update
-
Repeat until fully expanded:
- Continue expanding the subarray and updating the score until both
leftandrightcannot be moved further (i.e., until the subarray spans the entire array).
- Continue expanding the subarray and updating the score until both
-
Return the maximum score found:
- Once the loop completes, return
maxScoreas the maximum possible score of a "good" subarray.
- Once the loop completes, return
Algorithm Walkthrough
Let's consider the INput: nums = [4, 6, 4, 7, 2, 5, 1], k = 4
-
Initialization:
left = 4,right = 4,minVal = 2,maxScore = 2(sincenums[4] = 2).
-
First Expansion:
- Can move both
leftandright(since neither are at the array's ends). nums[3] = 7(left ofleft) is greater thannums[5] = 5(right ofright), so moveleftto 3.- Update
minValtomin(2, 7) = 2. - New score is
2 * (4 - 3 + 1) = 4. UpdatemaxScoreto4.
- Can move both
-
Second Expansion:
- Again, both
leftandrightcan move. nums[2] = 4(left ofleft) is less thannums[5] = 5, so moverightto 5.- Update
minValtomin(2, 5) = 2. - New score is
2 * (5 - 3 + 1) = 6. UpdatemaxScoreto6.
- Again, both
-
Third Expansion:
- Both
leftandrightcan still move. nums[1] = 6(left ofleft) is greater thannums[6] = 1(right ofright), so moveleftto 2.- Update
minValtomin(2, 4) = 2. - New score is
2 * (5 - 2 + 1) = 8. UpdatemaxScoreto8.
- Both
-
Fourth Expansion:
- Both pointers can move.
nums[0] = 4is greater thannums[6] = 1, so moveleftto 1.- Update
minValtomin(2, 6) = 2. - New score is
2 * (5 - 1 + 1) = 10. UpdatemaxScoreto10.
-
Fifth Expansion:
leftcan move (to 0), butrightcannot (already at the end).- Move
leftto 0. - Update
minValtomin(2, 4) = 2. - New score is
2 * (5 - 0 + 1) = 12. UpdatemaxScoreto12.
-
Completion:
- No further expansions are possible.
- The loop ends, and the method returns
maxScore = 12.
Code
Complexity Analysis
Time Complexity:
- The time complexity of the solution is
, where n is the number of elements in the input array nums. This is because, in the worst case, the algorithm expands the search space to include each element of the array once as it attempts to find the maximum score.
Space Complexity:
- The space complexity of the solution is
, as the solution uses a fixed amount of additional space regardless of the input size. The extra space is used for the pointers and variables to store the current minimum value, current score, and maximum score found so far.
On this page
Problem Statement
Examples
Solution
Step-by-Step Algorithm
Algorithm Walkthrough
Code
Complexity Analysis